/*
 * @lc app=leetcode.cn id=322 lang=javascript
 *
 * [322] 零钱兑换
 */

// @lc code=start
/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
var coinChange = function(coins, amount) {
    if(amount==0)return 0
    let db=[0]
    let numS=Infinity
    for(let i of coins){
        numS=Math.min(i,numS)
        db[i]=1
    }
    for(let i=numS+1;i<=amount;i++){
        db[i]=Infinity
        for(let j of coins){
            if(db[i-j]==0||db[i-j]){
                db[i]=Math.min(db[i-j]+1,db[i])
            }
        }
       
    }
    if(db[amount]!=Infinity&&db[amount]!=undefined){
        return db[amount]
    }
    return -1
};
// @lc code=end

coinChange ([1,2147483647])